<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222" media="(prefers-color-scheme: light)">
<meta name="theme-color" content="#222" media="(prefers-color-scheme: dark)"><meta name="generator" content="Hexo 5.2.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.1.2/css/all.min.css" integrity="sha256-xejo6yLi6vGtAjcMIsY8BHdKsLg7QynVlFMzdQgUuy8=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.5.7/jquery.fancybox.min.css" integrity="sha256-Vzbj7sDDS/woiFS3uNKo8eIuni59rjyNGtXfstRzStA=" crossorigin="anonymous">

<script class="next-config" data-name="main" type="application/json">{"hostname":"gz1234.gitee.io","root":"/","images":"/images","scheme":"Gemini","darkmode":true,"version":"8.12.3","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":{"enable":true,"style":"flat"},"bookmark":{"enable":true,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}}</script><script src="/js/config.js"></script>

    <meta name="description" content="算法思想 二分  双指针 （快慢指针 头尾指针） 1.链表 数组  递归 回溯 （画递归树） 123456function backTrack(数据， 路径缓存)&amp;#123; for (下一个值) 标记 backTrack 取消标记&amp;#125;  动态规划 找最优解  贪心  bfs(宽度优先) dfs(回溯 广度优先)">
<meta property="og:type" content="article">
<meta property="og:title" content="算法思想">
<meta property="og:url" content="https://gz1234.gitee.io/2022/07/27/%E7%AE%97%E6%B3%95%E6%80%9D%E6%83%B3/index.html">
<meta property="og:site_name" content="郭泽">
<meta property="og:description" content="算法思想 二分  双指针 （快慢指针 头尾指针） 1.链表 数组  递归 回溯 （画递归树） 123456function backTrack(数据， 路径缓存)&amp;#123; for (下一个值) 标记 backTrack 取消标记&amp;#125;  动态规划 找最优解  贪心  bfs(宽度优先) dfs(回溯 广度优先)">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://user-gold-cdn.xitu.io/2018/5/20/1637cba2a6155793?w=640&h=419&f=png&s=15737">
<meta property="og:image" content="https://user-gold-cdn.xitu.io/2018/5/22/16388487759b1152?w=1060&h=178&f=png&s=20820">
<meta property="og:image" content="https://user-gold-cdn.xitu.io/2018/5/22/163884f74c9f4e4d?w=320&h=267&f=png&s=11622">
<meta property="og:image" content="https://user-gold-cdn.xitu.io/2018/5/22/1638850ba7458208?w=596&h=485&f=png&s=36796">
<meta property="og:image" content="https://user-gold-cdn.xitu.io/2018/6/23/1642cc145a0cfb26?w=800&h=566&f=png&s=73573">
<meta property="og:image" content="https://user-gold-cdn.xitu.io/2018/6/9/163e1d2f6cec3348?w=640&h=600&f=png&s=48344">
<meta property="og:image" content="https://user-gold-cdn.xitu.io/2018/6/9/163e45b56fd25172?w=421&h=209&f=png&s=26545">
<meta property="og:image" content="https://user-gold-cdn.xitu.io/2018/6/15/164009e58a5a21f8?w=537&h=394&f=png&s=77222">
<meta property="article:published_time" content="2022-07-27T02:00:55.000Z">
<meta property="article:modified_time" content="2022-11-22T03:28:43.518Z">
<meta property="article:author" content="郭泽">
<meta property="article:tag" content="算法思想">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://user-gold-cdn.xitu.io/2018/5/20/1637cba2a6155793?w=640&h=419&f=png&s=15737">


<link rel="canonical" href="https://gz1234.gitee.io/2022/07/27/%E7%AE%97%E6%B3%95%E6%80%9D%E6%83%B3/">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"https://gz1234.gitee.io/2022/07/27/%E7%AE%97%E6%B3%95%E6%80%9D%E6%83%B3/","path":"2022/07/27/算法思想/","title":"算法思想"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>算法思想 | 郭泽</title>
  





  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">郭泽</p>
      <i class="logo-line"></i>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li><li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a></li><li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%AE%97%E6%B3%95%E6%80%9D%E6%83%B3"><span class="nav-number">1.</span> <span class="nav-text">算法思想</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="nav-number">2.</span> <span class="nav-text">数据结构</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B8%B8%E8%A7%81%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="nav-number">3.</span> <span class="nav-text">常见数据结构</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%A0%88"><span class="nav-number">4.</span> <span class="nav-text">栈</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A6%82%E5%BF%B5"><span class="nav-number">4.1.</span> <span class="nav-text">概念</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%AE%9E%E7%8E%B0"><span class="nav-number">4.2.</span> <span class="nav-text">实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%BA%94%E7%94%A8"><span class="nav-number">5.</span> <span class="nav-text">应用</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%98%9F%E5%88%97"><span class="nav-number">6.</span> <span class="nav-text">队列</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A6%82%E5%BF%B5-1"><span class="nav-number">6.1.</span> <span class="nav-text">概念</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%AE%9E%E7%8E%B0-1"><span class="nav-number">6.2.</span> <span class="nav-text">实现</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%8D%95%E9%93%BE%E9%98%9F%E5%88%97"><span class="nav-number">6.2.1.</span> <span class="nav-text">单链队列</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%BE%AA%E7%8E%AF%E9%98%9F%E5%88%97"><span class="nav-number">6.2.2.</span> <span class="nav-text">循环队列</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%93%BE%E8%A1%A8"><span class="nav-number">7.</span> <span class="nav-text">链表</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A6%82%E5%BF%B5-2"><span class="nav-number">7.1.</span> <span class="nav-text">概念</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%AE%9E%E7%8E%B0-2"><span class="nav-number">7.2.</span> <span class="nav-text">实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%A0%91"><span class="nav-number">8.</span> <span class="nav-text">树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="nav-number">8.1.</span> <span class="nav-text">二叉树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E6%A0%91"><span class="nav-number">8.2.</span> <span class="nav-text">二分搜索树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%AE%9E%E7%8E%B0-3"><span class="nav-number">8.3.</span> <span class="nav-text">实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#AVL-%E6%A0%91"><span class="nav-number">9.</span> <span class="nav-text">AVL 树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A6%82%E5%BF%B5-3"><span class="nav-number">9.1.</span> <span class="nav-text">概念</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%AE%9E%E7%8E%B0-4"><span class="nav-number">9.2.</span> <span class="nav-text">实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Trie"><span class="nav-number">10.</span> <span class="nav-text">Trie</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A6%82%E5%BF%B5-4"><span class="nav-number">10.1.</span> <span class="nav-text">概念</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%AE%9E%E7%8E%B0-5"><span class="nav-number">10.2.</span> <span class="nav-text">实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B9%B6%E6%9F%A5%E9%9B%86"><span class="nav-number">11.</span> <span class="nav-text">并查集</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A6%82%E5%BF%B5-5"><span class="nav-number">11.1.</span> <span class="nav-text">概念</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%AE%9E%E7%8E%B0-6"><span class="nav-number">11.2.</span> <span class="nav-text">实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%A0%86"><span class="nav-number">12.</span> <span class="nav-text">堆</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A6%82%E5%BF%B5-6"><span class="nav-number">12.1.</span> <span class="nav-text">概念</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%AE%9E%E7%8E%B0%E5%A4%A7%E6%A0%B9%E5%A0%86"><span class="nav-number">12.2.</span> <span class="nav-text">实现大根堆</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B0%BE%E8%B0%83%E7%94%A8"><span class="nav-number">13.</span> <span class="nav-text">尾调用</span></a></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">郭泽</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">54</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">21</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">51</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>



        </div>
      </div>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>
  <a role="button" class="book-mark-link book-mark-link-fixed"></a>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://gz1234.gitee.io/2022/07/27/%E7%AE%97%E6%B3%95%E6%80%9D%E6%83%B3/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="郭泽">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="郭泽">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="算法思想 | 郭泽">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          算法思想
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-07-27 10:00:55" itemprop="dateCreated datePublished" datetime="2022-07-27T10:00:55+08:00">2022-07-27</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2022-11-22 11:28:43" itemprop="dateModified" datetime="2022-11-22T11:28:43+08:00">2022-11-22</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95%E6%80%9D%E6%83%B3/" itemprop="url" rel="index"><span itemprop="name">算法思想</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h2 id="算法思想"><a href="#算法思想" class="headerlink" title="算法思想"></a>算法思想</h2><ul>
<li><p>二分</p>
</li>
<li><p>双指针 （快慢指针 头尾指针） 1.链表 数组</p>
</li>
<li><p>递归 回溯 （画递归树）</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">backTrack</span>(<span class="params">数据， 路径缓存</span>)</span>&#123;</span><br><span class="line"> <span class="keyword">for</span> (下一个值)</span><br><span class="line"> 标记</span><br><span class="line"> backTrack</span><br><span class="line"> 取消标记</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
<li><p>动态规划 找最优解</p>
</li>
<li><p>贪心</p>
</li>
<li><p>bfs(宽度优先) dfs(回溯 广度优先)</p>
</li>
</ul>
<a id="more"></a>

<h2 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h2><ul>
<li>链表</li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">遍历;</span><br><span class="line"></span><br><span class="line"><span class="keyword">while</span> (head) &#123;</span><br><span class="line">  head = head.next;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">return</span> head;</span><br><span class="line"><span class="comment">// 哨兵节点-中间节点</span></span><br><span class="line"><span class="keyword">let</span> dummny = &#123;</span><br><span class="line">  next: head,</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="keyword">return</span> dummny.next;</span><br></pre></td></tr></table></figure>

<ul>
<li>数组</li>
<li>树结构</li>
</ul>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">(二叉树)</span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">walk</span>(<span class="params">treeNode</span>)</span>&#123;</span><br><span class="line"></span><br><span class="line"> 终止条件 treeNode</span><br><span class="line"> walk(treeNode.left);</span><br><span class="line"> walk(treeNode.right)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"> walk(treeNode.left);</span><br><span class="line"> 终止条件 treeNode</span><br><span class="line"> walk(treeNode.right)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"> walk(treeNode.left);</span><br><span class="line"> walk(treeNode.right)</span><br><span class="line"> 终止条件 treeNode</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="常见数据结构"><a href="#常见数据结构" class="headerlink" title="常见数据结构"></a>常见数据结构</h2><h2 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h2><h3 id="概念"><a href="#概念" class="headerlink" title="概念"></a>概念</h3><p>栈是一个线性结构，在计算机中是一个相当常见的数据结构。</p>
<p>栈的特点是只能在某一端添加或删除数据，遵循先进后出的原则</p>
<h3 id="实现"><a href="#实现" class="headerlink" title="实现"></a>实现</h3><p>每种数据结构都可以用很多种方式来实现，其实可以把栈看成是数组的一个子集，所以这里使用数组来实现</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Stack</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.stack = []</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">push</span>(<span class="params">item</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.stack.push(item)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">pop</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.stack.pop()</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">peek</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.stack[<span class="built_in">this</span>.getCount() - <span class="number">1</span>]</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">getCount</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.stack.length</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">isEmpty</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.getCount() === <span class="number">0</span></span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="应用"><a href="#应用" class="headerlink" title="应用"></a>应用</h2><p>选取了 <a target="_blank" rel="noopener" href="https://leetcode.com/problems/valid-parentheses/submissions/1">LeetCode 上序号为 20 的题目</a></p>
<p>题意是匹配括号，可以通过栈的特性来完成这道题目</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> isValid = <span class="function"><span class="keyword">function</span> (<span class="params">s</span>) </span>&#123;</span><br><span class="line">  <span class="keyword">let</span> map = &#123;</span><br><span class="line">    <span class="string">&#x27;(&#x27;</span>: -<span class="number">1</span>,</span><br><span class="line">    <span class="string">&#x27;)&#x27;</span>: <span class="number">1</span>,</span><br><span class="line">    <span class="string">&#x27;[&#x27;</span>: -<span class="number">2</span>,</span><br><span class="line">    <span class="string">&#x27;]&#x27;</span>: <span class="number">2</span>,</span><br><span class="line">    <span class="string">&#x27;&#123;&#x27;</span>: -<span class="number">3</span>,</span><br><span class="line">    <span class="string">&#x27;&#125;&#x27;</span>: <span class="number">3</span></span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">let</span> stack = []</span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; s.length; i++) &#123;</span><br><span class="line">    <span class="keyword">if</span> (map[s[i]] &lt; <span class="number">0</span>) &#123;</span><br><span class="line">      stack.push(s[i])</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      <span class="keyword">let</span> last = stack.pop()</span><br><span class="line">      <span class="keyword">if</span> (map[last] + map[s[i]] != <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">if</span> (stack.length &gt; <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">  <span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="队列"><a href="#队列" class="headerlink" title="队列"></a>队列</h2><h3 id="概念-1"><a href="#概念-1" class="headerlink" title="概念"></a>概念</h3><p>队列是一个线性结构，特点是在某一端添加数据，在另一端删除数据，遵循先进先出的原则。</p>
<p><img src="https://user-gold-cdn.xitu.io/2018/5/20/1637cba2a6155793?w=640&h=419&f=png&s=15737"></p>
<h3 id="实现-1"><a href="#实现-1" class="headerlink" title="实现"></a>实现</h3><p>这里会讲解两种实现队列的方式，分别是单链队列和循环队列。</p>
<h4 id="单链队列"><a href="#单链队列" class="headerlink" title="单链队列"></a>单链队列</h4><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Queue</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.queue = []</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">enQueue</span>(<span class="params">item</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.queue.push(item)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">deQueue</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.queue.shift()</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">getHeader</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.queue[<span class="number">0</span>]</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">getLength</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.queue.length</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">isEmpty</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.getLength() === <span class="number">0</span></span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>因为单链队列在出队操作的时候需要 O(n) 的时间复杂度，所以引入了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度。</p>
<h4 id="循环队列"><a href="#循环队列" class="headerlink" title="循环队列"></a>循环队列</h4><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">SqQueue</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params">length</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.queue = <span class="keyword">new</span> <span class="built_in">Array</span>(length + <span class="number">1</span>)</span><br><span class="line">    <span class="comment">// 队头</span></span><br><span class="line">    <span class="built_in">this</span>.first = <span class="number">0</span></span><br><span class="line">    <span class="comment">// 队尾</span></span><br><span class="line">    <span class="built_in">this</span>.last = <span class="number">0</span></span><br><span class="line">    <span class="comment">// 当前队列大小</span></span><br><span class="line">    <span class="built_in">this</span>.size = <span class="number">0</span></span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">enQueue</span>(<span class="params">item</span>)</span> &#123;</span><br><span class="line">    <span class="comment">// 判断队尾 + 1 是否为队头</span></span><br><span class="line">    <span class="comment">// 如果是就代表需要扩容数组</span></span><br><span class="line">    <span class="comment">// % this.queue.length 是为了防止数组越界</span></span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">this</span>.first === (<span class="built_in">this</span>.last + <span class="number">1</span>) % <span class="built_in">this</span>.queue.length) &#123;</span><br><span class="line">      <span class="built_in">this</span>.resize(<span class="built_in">this</span>.getLength() * <span class="number">2</span> + <span class="number">1</span>)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">this</span>.queue[<span class="built_in">this</span>.last] = item</span><br><span class="line">    <span class="built_in">this</span>.size++</span><br><span class="line">    <span class="built_in">this</span>.last = (<span class="built_in">this</span>.last + <span class="number">1</span>) % <span class="built_in">this</span>.queue.length</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">deQueue</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">this</span>.isEmpty()) &#123;</span><br><span class="line">      <span class="keyword">throw</span> <span class="built_in">Error</span>(<span class="string">&#x27;Queue is empty&#x27;</span>)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">let</span> r = <span class="built_in">this</span>.queue[<span class="built_in">this</span>.first]</span><br><span class="line">    <span class="built_in">this</span>.queue[<span class="built_in">this</span>.first] = <span class="literal">null</span></span><br><span class="line">    <span class="built_in">this</span>.first = (<span class="built_in">this</span>.first + <span class="number">1</span>) % <span class="built_in">this</span>.queue.length</span><br><span class="line">    <span class="built_in">this</span>.size--</span><br><span class="line">    <span class="comment">// 判断当前队列大小是否过小</span></span><br><span class="line">    <span class="comment">// 为了保证不浪费空间，在队列空间等于总长度四分之一时</span></span><br><span class="line">    <span class="comment">// 且不为 2 时缩小总长度为当前的一半</span></span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">this</span>.size === <span class="built_in">this</span>.getLength() / <span class="number">4</span> &amp;&amp; <span class="built_in">this</span>.getLength() / <span class="number">2</span> !== <span class="number">0</span>) &#123;</span><br><span class="line">      <span class="built_in">this</span>.resize(<span class="built_in">this</span>.getLength() / <span class="number">2</span>)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> r</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">getHeader</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">this</span>.isEmpty()) &#123;</span><br><span class="line">      <span class="keyword">throw</span> <span class="built_in">Error</span>(<span class="string">&#x27;Queue is empty&#x27;</span>)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.queue[<span class="built_in">this</span>.first]</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">getLength</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.queue.length - <span class="number">1</span></span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">isEmpty</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.first === <span class="built_in">this</span>.last</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">resize</span>(<span class="params">length</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">let</span> q = <span class="keyword">new</span> <span class="built_in">Array</span>(length)</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; length; i++) &#123;</span><br><span class="line">      q[i] = <span class="built_in">this</span>.queue[(i + <span class="built_in">this</span>.first) % <span class="built_in">this</span>.queue.length]</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">this</span>.queue = q</span><br><span class="line">    <span class="built_in">this</span>.first = <span class="number">0</span></span><br><span class="line">    <span class="built_in">this</span>.last = <span class="built_in">this</span>.size</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="链表"><a href="#链表" class="headerlink" title="链表"></a>链表</h2><h3 id="概念-2"><a href="#概念-2" class="headerlink" title="概念"></a>概念</h3><p>链表是一个线性结构，同时也是一个天然的递归结构。链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。</p>
<p><img src="https://user-gold-cdn.xitu.io/2018/5/22/16388487759b1152?w=1060&h=178&f=png&s=20820"></p>
<h3 id="实现-2"><a href="#实现-2" class="headerlink" title="实现"></a>实现</h3><p><strong>单向链表</strong></p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Node</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params">v, next</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.value = v</span><br><span class="line">    <span class="built_in">this</span>.next = next</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">LinkList</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="comment">// 链表长度</span></span><br><span class="line">    <span class="built_in">this</span>.size = <span class="number">0</span></span><br><span class="line">    <span class="comment">// 虚拟头部</span></span><br><span class="line">    <span class="built_in">this</span>.dummyNode = <span class="keyword">new</span> Node(<span class="literal">null</span>, <span class="literal">null</span>)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">find</span>(<span class="params">header, index, currentIndex</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (index === currentIndex) <span class="keyword">return</span> header</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.find(header.next, index, currentIndex + <span class="number">1</span>)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">addNode</span>(<span class="params">v, index</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.checkIndex(index)</span><br><span class="line">    <span class="comment">// 当往链表末尾插入时，prev.next 为空</span></span><br><span class="line">    <span class="comment">// 其他情况时，因为要插入节点，所以插入的节点</span></span><br><span class="line">    <span class="comment">// 的 next 应该是 prev.next</span></span><br><span class="line">    <span class="comment">// 然后设置 prev.next 为插入的节点</span></span><br><span class="line">    <span class="keyword">let</span> prev = <span class="built_in">this</span>.find(<span class="built_in">this</span>.dummyNode, index, <span class="number">0</span>)</span><br><span class="line">    prev.next = <span class="keyword">new</span> Node(v, prev.next)</span><br><span class="line">    <span class="built_in">this</span>.size++</span><br><span class="line">    <span class="keyword">return</span> prev.next</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">insertNode</span>(<span class="params">v, index</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.addNode(v, index)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">addToFirst</span>(<span class="params">v</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.addNode(v, <span class="number">0</span>)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">addToLast</span>(<span class="params">v</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.addNode(v, <span class="built_in">this</span>.size)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">removeNode</span>(<span class="params">index, isLast</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.checkIndex(index)</span><br><span class="line">    index = isLast ? index - <span class="number">1</span> : index</span><br><span class="line">    <span class="keyword">let</span> prev = <span class="built_in">this</span>.find(<span class="built_in">this</span>.dummyNode, index, <span class="number">0</span>)</span><br><span class="line">    <span class="keyword">let</span> node = prev.next</span><br><span class="line">    prev.next = node.next</span><br><span class="line">    node.next = <span class="literal">null</span></span><br><span class="line">    <span class="built_in">this</span>.size--</span><br><span class="line">    <span class="keyword">return</span> node</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">removeFirstNode</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.removeNode(<span class="number">0</span>)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">removeLastNode</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.removeNode(<span class="built_in">this</span>.size, <span class="literal">true</span>)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">checkIndex</span>(<span class="params">index</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (index &lt; <span class="number">0</span> || index &gt; <span class="built_in">this</span>.size) <span class="keyword">throw</span> <span class="built_in">Error</span>(<span class="string">&#x27;Index error&#x27;</span>)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">getNode</span>(<span class="params">index</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.checkIndex(index)</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">this</span>.isEmpty()) <span class="keyword">return</span></span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.find(<span class="built_in">this</span>.dummyNode, index, <span class="number">0</span>).next</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">isEmpty</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.size === <span class="number">0</span></span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">getSize</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.size</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="树"><a href="#树" class="headerlink" title="树"></a>树</h2><h3 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h3><p>树拥有很多种结构，二叉树是树中最常用的结构，同时也是一个天然的递归结构。</p>
<p>二叉树拥有一个根节点，每个节点至多拥有两个子节点，分别为：左节点和右节点。树的最底部节点称之为叶节点，当一颗树的叶数量数量为满时，该树可以称之为满二叉树。</p>
<p><img src="https://user-gold-cdn.xitu.io/2018/5/22/163884f74c9f4e4d?w=320&h=267&f=png&s=11622"></p>
<h3 id="二分搜索树"><a href="#二分搜索树" class="headerlink" title="二分搜索树"></a>二分搜索树</h3><p>二分搜索树也是二叉树，拥有二叉树的特性。但是区别在于二分搜索树每个节点的值都比他的左子树的值大，比右子树的值小。</p>
<p>这种存储方式很适合于数据搜索。如下图所示，当需要查找 6 的时候，因为需要查找的值比根节点的值大，所以只需要在根节点的右子树上寻找，大大提高了搜索效率。</p>
<p><img src="https://user-gold-cdn.xitu.io/2018/5/22/1638850ba7458208?w=596&h=485&f=png&s=36796"></p>
<h3 id="实现-3"><a href="#实现-3" class="headerlink" title="实现"></a>实现</h3><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Node</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params">value</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.value = value</span><br><span class="line">    <span class="built_in">this</span>.left = <span class="literal">null</span></span><br><span class="line">    <span class="built_in">this</span>.right = <span class="literal">null</span></span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">BST</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.root = <span class="literal">null</span></span><br><span class="line">    <span class="built_in">this</span>.size = <span class="number">0</span></span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">getSize</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.size</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">isEmpty</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.size === <span class="number">0</span></span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">addNode</span>(<span class="params">v</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.root = <span class="built_in">this</span>._addChild(<span class="built_in">this</span>.root, v)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="comment">// 添加节点时，需要比较添加的节点值和当前</span></span><br><span class="line">  <span class="comment">// 节点值的大小</span></span><br><span class="line">  <span class="function"><span class="title">_addChild</span>(<span class="params">node, v</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (!node) &#123;</span><br><span class="line">      <span class="built_in">this</span>.size++</span><br><span class="line">      <span class="keyword">return</span> <span class="keyword">new</span> Node(v)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (node.value &gt; v) &#123;</span><br><span class="line">      node.left = <span class="built_in">this</span>._addChild(node.left, v)</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (node.value &lt; v) &#123;</span><br><span class="line">      node.right = <span class="built_in">this</span>._addChild(node.right, v)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> node</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>以上是最基本的二分搜索树实现，接下来实现树的遍历。</p>
<p>对于树的遍历来说，有三种遍历方法，分别是先序遍历、中序遍历、后序遍历。三种遍历的区别在于何时访问节点。在遍历树的过程中，每个节点都会遍历三次，分别是遍历到自己，遍历左子树和遍历右子树。如果需要实现先序遍历，那么只需要第一次遍历到节点时进行操作即可。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 先序遍历可用于打印树的结构</span></span><br><span class="line"><span class="comment">// 先序遍历先访问根节点，然后访问左节点，最后访问右节点。</span></span><br><span class="line"><span class="function"><span class="title">preTraversal</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">  <span class="built_in">this</span>._pre(<span class="built_in">this</span>.root)</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="title">_pre</span>(<span class="params">node</span>)</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (node) &#123;</span><br><span class="line">    <span class="built_in">console</span>.log(node.value)</span><br><span class="line">    <span class="built_in">this</span>._pre(node.left)</span><br><span class="line">    <span class="built_in">this</span>._pre(node.right)</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 中序遍历可用于排序</span></span><br><span class="line"><span class="comment">// 对于 BST 来说，中序遍历可以实现一次遍历就</span></span><br><span class="line"><span class="comment">// 得到有序的值</span></span><br><span class="line"><span class="comment">// 中序遍历表示先访问左节点，然后访问根节点，最后访问右节点。</span></span><br><span class="line"><span class="function"><span class="title">midTraversal</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">  <span class="built_in">this</span>._mid(<span class="built_in">this</span>.root)</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="title">_mid</span>(<span class="params">node</span>)</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (node) &#123;</span><br><span class="line">    <span class="built_in">this</span>._mid(node.left)</span><br><span class="line">    <span class="built_in">console</span>.log(node.value)</span><br><span class="line">    <span class="built_in">this</span>._mid(node.right)</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 后序遍历可用于先操作子节点</span></span><br><span class="line"><span class="comment">// 再操作父节点的场景</span></span><br><span class="line"><span class="comment">// 后序遍历表示先访问左节点，然后访问右节点，最后访问根节点。</span></span><br><span class="line"><span class="function"><span class="title">backTraversal</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">  <span class="built_in">this</span>._back(<span class="built_in">this</span>.root)</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="title">_back</span>(<span class="params">node</span>)</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (node) &#123;</span><br><span class="line">    <span class="built_in">this</span>._back(node.left)</span><br><span class="line">    <span class="built_in">this</span>._back(node.right)</span><br><span class="line">    <span class="built_in">console</span>.log(node.value)</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>以上的这几种遍历都可以称之为深度遍历，对应的还有种遍历叫做广度遍历，也就是一层层地遍历树。对于广度遍历来说，我们需要利用之前讲过的队列结构来完成。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="title">breadthTraversal</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (!<span class="built_in">this</span>.root) <span class="keyword">return</span> <span class="literal">null</span></span><br><span class="line">  <span class="keyword">let</span> q = <span class="keyword">new</span> Queue()</span><br><span class="line">  <span class="comment">// 将根节点入队</span></span><br><span class="line">  q.enQueue(<span class="built_in">this</span>.root)</span><br><span class="line">  <span class="comment">// 循环判断队列是否为空，为空</span></span><br><span class="line">  <span class="comment">// 代表树遍历完毕</span></span><br><span class="line">  <span class="keyword">while</span> (!q.isEmpty()) &#123;</span><br><span class="line">    <span class="comment">// 将队首出队，判断是否有左右子树</span></span><br><span class="line">    <span class="comment">// 有的话，就先左后右入队</span></span><br><span class="line">    <span class="keyword">let</span> n = q.deQueue()</span><br><span class="line">    <span class="built_in">console</span>.log(n.value)</span><br><span class="line">    <span class="keyword">if</span> (n.left) q.enQueue(n.left)</span><br><span class="line">    <span class="keyword">if</span> (n.right) q.enQueue(n.right)</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>接下来先介绍如何在树中寻找最小值或最大数。因为二分搜索树的特性，所以最小值一定在根节点的最左边，最大值相反</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="title">getMin</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">  <span class="keyword">return</span> <span class="built_in">this</span>._getMin(<span class="built_in">this</span>.root).value</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="title">_getMin</span>(<span class="params">node</span>)</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (!node.left) <span class="keyword">return</span> node</span><br><span class="line">  <span class="keyword">return</span> <span class="built_in">this</span>._getMin(node.left)</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="title">getMax</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">  <span class="keyword">return</span> <span class="built_in">this</span>._getMax(<span class="built_in">this</span>.root).value</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="title">_getMax</span>(<span class="params">node</span>)</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (!node.right) <span class="keyword">return</span> node</span><br><span class="line">  <span class="keyword">return</span> <span class="built_in">this</span>._getMin(node.right)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>向上取整和向下取整</strong>，这两个操作是相反的，所以代码也是类似的，这里只介绍如何向下取整。既然是向下取整，那么根据二分搜索树的特性，值一定在根节点的左侧。只需要一直遍历左子树直到当前节点的值不再大于等于需要的值，然后判断节点是否还拥有右子树。如果有的话，继续上面的递归判断。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="title">floor</span>(<span class="params">v</span>)</span> &#123;</span><br><span class="line">  <span class="keyword">let</span> node = <span class="built_in">this</span>._floor(<span class="built_in">this</span>.root, v)</span><br><span class="line">  <span class="keyword">return</span> node ? node.value : <span class="literal">null</span></span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="title">_floor</span>(<span class="params">node, v</span>)</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (!node) <span class="keyword">return</span> <span class="literal">null</span></span><br><span class="line">  <span class="keyword">if</span> (node.value === v) <span class="keyword">return</span> v</span><br><span class="line">  <span class="comment">// 如果当前节点值还比需要的值大，就继续递归</span></span><br><span class="line">  <span class="keyword">if</span> (node.value &gt; v) &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>._floor(node.left, v)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="comment">// 判断当前节点是否拥有右子树</span></span><br><span class="line">  <span class="keyword">let</span> right = <span class="built_in">this</span>._floor(node.right, v)</span><br><span class="line">  <span class="keyword">if</span> (right) <span class="keyword">return</span> right</span><br><span class="line">  <span class="keyword">return</span> node</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>排名</strong>，这是用于获取给定值的排名或者排名第几的节点的值，这两个操作也是相反的，所以这个只介绍如何获取排名第几的节点的值。对于这个操作而言，我们需要略微的改造点代码，让每个节点拥有一个 <code>size</code> 属性。该属性表示该节点下有多少子节点（包含自身）。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Node</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params">value</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.value = value</span><br><span class="line">    <span class="built_in">this</span>.left = <span class="literal">null</span></span><br><span class="line">    <span class="built_in">this</span>.right = <span class="literal">null</span></span><br><span class="line">    <span class="comment">// 修改代码</span></span><br><span class="line">    <span class="built_in">this</span>.size = <span class="number">1</span></span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 新增代码</span></span><br><span class="line"><span class="function"><span class="title">_getSize</span>(<span class="params">node</span>)</span> &#123;</span><br><span class="line">  <span class="keyword">return</span> node ? node.size : <span class="number">0</span></span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="title">_addChild</span>(<span class="params">node, v</span>)</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (!node) &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> Node(v)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">if</span> (node.value &gt; v) &#123;</span><br><span class="line">    <span class="comment">// 修改代码</span></span><br><span class="line">    node.size++</span><br><span class="line">    node.left = <span class="built_in">this</span>._addChild(node.left, v)</span><br><span class="line">  &#125; <span class="keyword">else</span> <span class="keyword">if</span> (node.value &lt; v) &#123;</span><br><span class="line">    <span class="comment">// 修改代码</span></span><br><span class="line">    node.size++</span><br><span class="line">    node.right = <span class="built_in">this</span>._addChild(node.right, v)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> node</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="title">select</span>(<span class="params">k</span>)</span> &#123;</span><br><span class="line">  <span class="keyword">let</span> node = <span class="built_in">this</span>._select(<span class="built_in">this</span>.root, k)</span><br><span class="line">  <span class="keyword">return</span> node ? node.value : <span class="literal">null</span></span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="title">_select</span>(<span class="params">node, k</span>)</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (!node) <span class="keyword">return</span> <span class="literal">null</span></span><br><span class="line">  <span class="comment">// 先获取左子树下有几个节点</span></span><br><span class="line">  <span class="keyword">let</span> size = node.left ? node.left.size : <span class="number">0</span></span><br><span class="line">  <span class="comment">// 判断 size 是否大于 k</span></span><br><span class="line">  <span class="comment">// 如果大于 k，代表所需要的节点在左节点</span></span><br><span class="line">  <span class="keyword">if</span> (size &gt; k) <span class="keyword">return</span> <span class="built_in">this</span>._select(node.left, k)</span><br><span class="line">  <span class="comment">// 如果小于 k，代表所需要的节点在右节点</span></span><br><span class="line">  <span class="comment">// 注意这里需要重新计算 k，减去根节点除了右子树的节点数量</span></span><br><span class="line">  <span class="keyword">if</span> (size &lt; k) <span class="keyword">return</span> <span class="built_in">this</span>._select(node.right, k - size - <span class="number">1</span>)</span><br><span class="line">  <span class="keyword">return</span> node</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>接下来讲解的是二分搜索树中最难实现的部分：删除节点。因为对于删除节点来说，会存在以下几种情况</p>
<ul>
<li>需要删除的节点没有子树</li>
<li>需要删除的节点只有一条子树</li>
<li>需要删除的节点有左右两条树</li>
</ul>
<p>对于前两种情况很好解决，但是第三种情况就有难度了，所以先来实现相对简单的操作：删除最小节点，对于删除最小节点来说，是不存在第三种情况的，删除最大节点操作是和删除最小节点相反的，所以这里也就不再赘述。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="title">delectMin</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">  <span class="built_in">this</span>.root = <span class="built_in">this</span>._delectMin(<span class="built_in">this</span>.root)</span><br><span class="line">  <span class="built_in">console</span>.log(<span class="built_in">this</span>.root)</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="title">_delectMin</span>(<span class="params">node</span>)</span> &#123;</span><br><span class="line">  <span class="comment">// 一直递归左子树</span></span><br><span class="line">  <span class="comment">// 如果左子树为空，就判断节点是否拥有右子树</span></span><br><span class="line">  <span class="comment">// 有右子树的话就把需要删除的节点替换为右子树</span></span><br><span class="line">  <span class="keyword">if</span> ((node != <span class="literal">null</span>) &amp; !node.left) <span class="keyword">return</span> node.right</span><br><span class="line">  node.left = <span class="built_in">this</span>._delectMin(node.left)</span><br><span class="line">  <span class="comment">// 最后需要重新维护下节点的 `size`</span></span><br><span class="line">  node.size = <span class="built_in">this</span>._getSize(node.left) + <span class="built_in">this</span>._getSize(node.right) + <span class="number">1</span></span><br><span class="line">  <span class="keyword">return</span> node</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>最后讲解的就是如何删除任意节点了。对于这个操作，T.Hibbard 在 1962 年提出了解决这个难题的办法，也就是如何解决第三种情况。</p>
<p>当遇到这种情况时，需要取出当前节点的后继节点（也就是当前节点右子树的最小节点）来替换需要删除的节点。然后将需要删除节点的左子树赋值给后继结点，右子树删除后继结点后赋值给他。</p>
<p>你如果对于这个解决办法有疑问的话，可以这样考虑。因为二分搜索树的特性，父节点一定比所有左子节点大，比所有右子节点小。那么当需要删除父节点时，势必需要拿出一个比父节点大的节点来替换父节点。这个节点肯定不存在于左子树，必然存在于右子树。然后又需要保持父节点都是比右子节点小的，那么就可以取出右子树中最小的那个节点来替换父节点。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="title">delect</span>(<span class="params">v</span>)</span> &#123;</span><br><span class="line">  <span class="built_in">this</span>.root = <span class="built_in">this</span>._delect(<span class="built_in">this</span>.root, v)</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="title">_delect</span>(<span class="params">node, v</span>)</span> &#123;</span><br><span class="line">  <span class="keyword">if</span> (!node) <span class="keyword">return</span> <span class="literal">null</span></span><br><span class="line">  <span class="comment">// 寻找的节点比当前节点小，去左子树找</span></span><br><span class="line">  <span class="keyword">if</span> (node.value &lt; v) &#123;</span><br><span class="line">    node.right = <span class="built_in">this</span>._delect(node.right, v)</span><br><span class="line">  &#125; <span class="keyword">else</span> <span class="keyword">if</span> (node.value &gt; v) &#123;</span><br><span class="line">    <span class="comment">// 寻找的节点比当前节点大，去右子树找</span></span><br><span class="line">    node.left = <span class="built_in">this</span>._delect(node.left, v)</span><br><span class="line">  &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">    <span class="comment">// 进入这个条件说明已经找到节点</span></span><br><span class="line">    <span class="comment">// 先判断节点是否拥有拥有左右子树中的一个</span></span><br><span class="line">    <span class="comment">// 是的话，将子树返回出去，这里和 `_delectMin` 的操作一样</span></span><br><span class="line">    <span class="keyword">if</span> (!node.left) <span class="keyword">return</span> node.right</span><br><span class="line">    <span class="keyword">if</span> (!node.right) <span class="keyword">return</span> node.left</span><br><span class="line">    <span class="comment">// 进入这里，代表节点拥有左右子树</span></span><br><span class="line">    <span class="comment">// 先取出当前节点的后继结点，也就是取当前节点右子树的最小值</span></span><br><span class="line">    <span class="keyword">let</span> min = <span class="built_in">this</span>._getMin(node.right)</span><br><span class="line">    <span class="comment">// 取出最小值后，删除最小值</span></span><br><span class="line">    <span class="comment">// 然后把删除节点后的子树赋值给最小值节点</span></span><br><span class="line">    min.right = <span class="built_in">this</span>._delectMin(node.right)</span><br><span class="line">    <span class="comment">// 左子树不动</span></span><br><span class="line">    min.left = node.left</span><br><span class="line">    node = min</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="comment">// 维护 size</span></span><br><span class="line">  node.size = <span class="built_in">this</span>._getSize(node.left) + <span class="built_in">this</span>._getSize(node.right) + <span class="number">1</span></span><br><span class="line">  <span class="keyword">return</span> node</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="AVL-树"><a href="#AVL-树" class="headerlink" title="AVL 树"></a>AVL 树</h2><h3 id="概念-3"><a href="#概念-3" class="headerlink" title="概念"></a>概念</h3><p>二分搜索树实际在业务中是受到限制的，因为并不是严格的 O(logN)，在极端情况下会退化成链表，比如加入一组升序的数字就会造成这种情况。</p>
<p>AVL 树改进了二分搜索树，在 AVL 树中任意节点的左右子树的高度差都不大于 1，这样保证了时间复杂度是严格的 O(logN)。基于此，对 AVL 树增加或删除节点时可能需要旋转树来达到高度的平衡。</p>
<h3 id="实现-4"><a href="#实现-4" class="headerlink" title="实现"></a>实现</h3><p>因为 AVL 树是改进了二分搜索树，所以部分代码是于二分搜索树重复的，对于重复内容不作再次解析。</p>
<p>对于 AVL 树来说，添加节点会有四种情况</p>
<p><img src="https://user-gold-cdn.xitu.io/2018/6/23/1642cc145a0cfb26?w=800&h=566&f=png&s=73573"></p>
<p>对于左左情况来说，新增加的节点位于节点 2 的左侧，这时树已经不平衡，需要旋转。因为搜索树的特性，节点比左节点大，比右节点小，所以旋转以后也要实现这个特性。</p>
<p>旋转之前：new &lt; 2 &lt; C &lt; 3 &lt; B &lt; 5 &lt; A，右旋之后节点 3 为根节点，这时候需要将节点 3 的右节点加到节点 5 的左边，最后还需要更新节点的高度。</p>
<p>对于右右情况来说，相反于左左情况，所以不再赘述。</p>
<p>对于左右情况来说，新增加的节点位于节点 4 的右侧。对于这种情况，需要通过两次旋转来达到目的。</p>
<p>首先对节点的左节点左旋，这时树满足左左的情况，再对节点进行一次右旋就可以达到目的。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Node</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params">value</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.value = value</span><br><span class="line">    <span class="built_in">this</span>.left = <span class="literal">null</span></span><br><span class="line">    <span class="built_in">this</span>.right = <span class="literal">null</span></span><br><span class="line">    <span class="built_in">this</span>.height = <span class="number">1</span></span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">AVL</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.root = <span class="literal">null</span></span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">addNode</span>(<span class="params">v</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.root = <span class="built_in">this</span>._addChild(<span class="built_in">this</span>.root, v)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">_addChild</span>(<span class="params">node, v</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (!node) &#123;</span><br><span class="line">      <span class="keyword">return</span> <span class="keyword">new</span> Node(v)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (node.value &gt; v) &#123;</span><br><span class="line">      node.left = <span class="built_in">this</span>._addChild(node.left, v)</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (node.value &lt; v) &#123;</span><br><span class="line">      node.right = <span class="built_in">this</span>._addChild(node.right, v)</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      node.value = v</span><br><span class="line">    &#125;</span><br><span class="line">    node.height =</span><br><span class="line">      <span class="number">1</span> + <span class="built_in">Math</span>.max(<span class="built_in">this</span>._getHeight(node.left), <span class="built_in">this</span>._getHeight(node.right))</span><br><span class="line">    <span class="keyword">let</span> factor = <span class="built_in">this</span>._getBalanceFactor(node)</span><br><span class="line">    <span class="comment">// 当需要右旋时，根节点的左树一定比右树高度高</span></span><br><span class="line">    <span class="keyword">if</span> (factor &gt; <span class="number">1</span> &amp;&amp; <span class="built_in">this</span>._getBalanceFactor(node.left) &gt;= <span class="number">0</span>) &#123;</span><br><span class="line">      <span class="keyword">return</span> <span class="built_in">this</span>._rightRotate(node)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 当需要左旋时，根节点的左树一定比右树高度矮</span></span><br><span class="line">    <span class="keyword">if</span> (factor &lt; -<span class="number">1</span> &amp;&amp; <span class="built_in">this</span>._getBalanceFactor(node.right) &lt;= <span class="number">0</span>) &#123;</span><br><span class="line">      <span class="keyword">return</span> <span class="built_in">this</span>._leftRotate(node)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 左右情况</span></span><br><span class="line">    <span class="comment">// 节点的左树比右树高，且节点的左树的右树比节点的左树的左树高</span></span><br><span class="line">    <span class="keyword">if</span> (factor &gt; <span class="number">1</span> &amp;&amp; <span class="built_in">this</span>._getBalanceFactor(node.left) &lt; <span class="number">0</span>) &#123;</span><br><span class="line">      node.left = <span class="built_in">this</span>._leftRotate(node.left)</span><br><span class="line">      <span class="keyword">return</span> <span class="built_in">this</span>._rightRotate(node)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 右左情况</span></span><br><span class="line">    <span class="comment">// 节点的左树比右树矮，且节点的右树的右树比节点的右树的左树矮</span></span><br><span class="line">    <span class="keyword">if</span> (factor &lt; -<span class="number">1</span> &amp;&amp; <span class="built_in">this</span>._getBalanceFactor(node.right) &gt; <span class="number">0</span>) &#123;</span><br><span class="line">      node.right = <span class="built_in">this</span>._rightRotate(node.right)</span><br><span class="line">      <span class="keyword">return</span> <span class="built_in">this</span>._leftRotate(node)</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> node</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">_getHeight</span>(<span class="params">node</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (!node) <span class="keyword">return</span> <span class="number">0</span></span><br><span class="line">    <span class="keyword">return</span> node.height</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">_getBalanceFactor</span>(<span class="params">node</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>._getHeight(node.left) - <span class="built_in">this</span>._getHeight(node.right)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="comment">// 节点右旋</span></span><br><span class="line">  <span class="comment">//           5                    2</span></span><br><span class="line">  <span class="comment">//         /   \                /   \</span></span><br><span class="line">  <span class="comment">//        2     6   ==&gt;       1      5</span></span><br><span class="line">  <span class="comment">//       /  \               /       /  \</span></span><br><span class="line">  <span class="comment">//      1    3             new     3    6</span></span><br><span class="line">  <span class="comment">//     /</span></span><br><span class="line">  <span class="comment">//    new</span></span><br><span class="line">  <span class="function"><span class="title">_rightRotate</span>(<span class="params">node</span>)</span> &#123;</span><br><span class="line">    <span class="comment">// 旋转后新根节点</span></span><br><span class="line">    <span class="keyword">let</span> newRoot = node.left</span><br><span class="line">    <span class="comment">// 需要移动的节点</span></span><br><span class="line">    <span class="keyword">let</span> moveNode = newRoot.right</span><br><span class="line">    <span class="comment">// 节点 2 的右节点改为节点 5</span></span><br><span class="line">    newRoot.right = node</span><br><span class="line">    <span class="comment">// 节点 5 左节点改为节点 3</span></span><br><span class="line">    node.left = moveNode</span><br><span class="line">    <span class="comment">// 更新树的高度</span></span><br><span class="line">    node.height =</span><br><span class="line">      <span class="number">1</span> + <span class="built_in">Math</span>.max(<span class="built_in">this</span>._getHeight(node.left), <span class="built_in">this</span>._getHeight(node.right))</span><br><span class="line">    newRoot.height =</span><br><span class="line">      <span class="number">1</span> +</span><br><span class="line">      <span class="built_in">Math</span>.max(<span class="built_in">this</span>._getHeight(newRoot.left), <span class="built_in">this</span>._getHeight(newRoot.right))</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> newRoot</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="comment">// 节点左旋</span></span><br><span class="line">  <span class="comment">//           4                    6</span></span><br><span class="line">  <span class="comment">//         /   \                /   \</span></span><br><span class="line">  <span class="comment">//        2     6   ==&gt;       4      7</span></span><br><span class="line">  <span class="comment">//             /  \         /   \      \</span></span><br><span class="line">  <span class="comment">//            5     7      2     5      new</span></span><br><span class="line">  <span class="comment">//                   \</span></span><br><span class="line">  <span class="comment">//                    new</span></span><br><span class="line">  <span class="function"><span class="title">_leftRotate</span>(<span class="params">node</span>)</span> &#123;</span><br><span class="line">    <span class="comment">// 旋转后新根节点</span></span><br><span class="line">    <span class="keyword">let</span> newRoot = node.right</span><br><span class="line">    <span class="comment">// 需要移动的节点</span></span><br><span class="line">    <span class="keyword">let</span> moveNode = newRoot.left</span><br><span class="line">    <span class="comment">// 节点 6 的左节点改为节点 4</span></span><br><span class="line">    newRoot.left = node</span><br><span class="line">    <span class="comment">// 节点 4 右节点改为节点 5</span></span><br><span class="line">    node.right = moveNode</span><br><span class="line">    <span class="comment">// 更新树的高度</span></span><br><span class="line">    node.height =</span><br><span class="line">      <span class="number">1</span> + <span class="built_in">Math</span>.max(<span class="built_in">this</span>._getHeight(node.left), <span class="built_in">this</span>._getHeight(node.right))</span><br><span class="line">    newRoot.height =</span><br><span class="line">      <span class="number">1</span> +</span><br><span class="line">      <span class="built_in">Math</span>.max(<span class="built_in">this</span>._getHeight(newRoot.left), <span class="built_in">this</span>._getHeight(newRoot.right))</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> newRoot</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="Trie"><a href="#Trie" class="headerlink" title="Trie"></a>Trie</h2><h3 id="概念-4"><a href="#概念-4" class="headerlink" title="概念"></a>概念</h3><p>在计算机科学，<strong>trie</strong>，又称<strong>前缀树</strong>或<strong>字典树</strong>，是一种有序树，用于保存关联数组，其中的键通常是字符串。</p>
<p>简单点来说，这个结构的作用大多是为了方便搜索字符串，该树有以下几个特点</p>
<ul>
<li>根节点代表空字符串，每个节点都有 N（假如搜索英文字符，就有 26 条） 条链接，每条链接代表一个字符</li>
<li>节点不存储字符，只有路径才存储，这点和其他的树结构不同</li>
<li>从根节点开始到任意一个节点，将沿途经过的字符连接起来就是该节点对应的字符串</li>
</ul>
<p><img src="https://user-gold-cdn.xitu.io/2018/6/9/163e1d2f6cec3348?w=640&h=600&f=png&s=48344">、</p>
<h3 id="实现-5"><a href="#实现-5" class="headerlink" title="实现"></a>实现</h3><p>总得来说 Trie 的实现相比别的树结构来说简单的很多，实现就以搜索英文字符为例。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">TrieNode</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="comment">// 代表每个字符经过节点的次数</span></span><br><span class="line">    <span class="built_in">this</span>.path = <span class="number">0</span></span><br><span class="line">    <span class="comment">// 代表到该节点的字符串有几个</span></span><br><span class="line">    <span class="built_in">this</span>.end = <span class="number">0</span></span><br><span class="line">    <span class="comment">// 链接</span></span><br><span class="line">    <span class="built_in">this</span>.next = <span class="keyword">new</span> <span class="built_in">Array</span>(<span class="number">26</span>).fill(<span class="literal">null</span>)</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Trie</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="comment">// 根节点，代表空字符</span></span><br><span class="line">    <span class="built_in">this</span>.root = <span class="keyword">new</span> TrieNode()</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="comment">// 插入字符串</span></span><br><span class="line">  <span class="function"><span class="title">insert</span>(<span class="params">str</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (!str) <span class="keyword">return</span></span><br><span class="line">    <span class="keyword">let</span> node = <span class="built_in">this</span>.root</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; str.length; i++) &#123;</span><br><span class="line">      <span class="comment">// 获得字符先对应的索引</span></span><br><span class="line">      <span class="keyword">let</span> index = str[i].charCodeAt() - <span class="string">&#x27;a&#x27;</span>.charCodeAt()</span><br><span class="line">      <span class="comment">// 如果索引对应没有值，就创建</span></span><br><span class="line">      <span class="keyword">if</span> (!node.next[index]) &#123;</span><br><span class="line">        node.next[index] = <span class="keyword">new</span> TrieNode()</span><br><span class="line">      &#125;</span><br><span class="line">      node.path += <span class="number">1</span></span><br><span class="line">      node = node.next[index]</span><br><span class="line">    &#125;</span><br><span class="line">    node.end += <span class="number">1</span></span><br><span class="line">  &#125;</span><br><span class="line">  <span class="comment">// 搜索字符串出现的次数</span></span><br><span class="line">  <span class="function"><span class="title">search</span>(<span class="params">str</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (!str) <span class="keyword">return</span></span><br><span class="line">    <span class="keyword">let</span> node = <span class="built_in">this</span>.root</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; str.length; i++) &#123;</span><br><span class="line">      <span class="keyword">let</span> index = str[i].charCodeAt() - <span class="string">&#x27;a&#x27;</span>.charCodeAt()</span><br><span class="line">      <span class="comment">// 如果索引对应没有值，代表没有需要搜素的字符串</span></span><br><span class="line">      <span class="keyword">if</span> (!node.next[index]) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span></span><br><span class="line">      &#125;</span><br><span class="line">      node = node.next[index]</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> node.end</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="comment">// 删除字符串</span></span><br><span class="line">  <span class="function"><span class="title">delete</span>(<span class="params">str</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (!<span class="built_in">this</span>.search(str)) <span class="keyword">return</span></span><br><span class="line">    <span class="keyword">let</span> node = <span class="built_in">this</span>.root</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; str.length; i++) &#123;</span><br><span class="line">      <span class="keyword">let</span> index = str[i].charCodeAt() - <span class="string">&#x27;a&#x27;</span>.charCodeAt()</span><br><span class="line">      <span class="comment">// 如果索引对应的节点的 Path 为 0，代表经过该节点的字符串</span></span><br><span class="line">      <span class="comment">// 已经一个，直接删除即可</span></span><br><span class="line">      <span class="keyword">if</span> (--node.next[index].path == <span class="number">0</span>) &#123;</span><br><span class="line">        node.next[index] = <span class="literal">null</span></span><br><span class="line">        <span class="keyword">return</span></span><br><span class="line">      &#125;</span><br><span class="line">      node = node.next[index]</span><br><span class="line">    &#125;</span><br><span class="line">    node.end -= <span class="number">1</span></span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="并查集"><a href="#并查集" class="headerlink" title="并查集"></a>并查集</h2><h3 id="概念-5"><a href="#概念-5" class="headerlink" title="概念"></a>概念</h3><p>并查集是一种特殊的树结构，用于处理一些不交集的合并及查询问题。该结构中每个节点都有一个父节点，如果只有当前一个节点，那么该节点的父节点指向自己。</p>
<p>这个结构中有两个重要的操作，分别是：</p>
<ul>
<li>Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。</li>
<li>Union：将两个子集合并成同一个集合。</li>
</ul>
<p><img src="https://user-gold-cdn.xitu.io/2018/6/9/163e45b56fd25172?w=421&h=209&f=png&s=26545"></p>
<h3 id="实现-6"><a href="#实现-6" class="headerlink" title="实现"></a>实现</h3><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">DisjointSet</span> </span>&#123;</span><br><span class="line">  <span class="comment">// 初始化样本</span></span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params">count</span>)</span> &#123;</span><br><span class="line">    <span class="comment">// 初始化时，每个节点的父节点都是自己</span></span><br><span class="line">    <span class="built_in">this</span>.parent = <span class="keyword">new</span> <span class="built_in">Array</span>(count)</span><br><span class="line">    <span class="comment">// 用于记录树的深度，优化搜索复杂度</span></span><br><span class="line">    <span class="built_in">this</span>.rank = <span class="keyword">new</span> <span class="built_in">Array</span>(count)</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; count; i++) &#123;</span><br><span class="line">      <span class="built_in">this</span>.parent[i] = i</span><br><span class="line">      <span class="built_in">this</span>.rank[i] = <span class="number">1</span></span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">find</span>(<span class="params">p</span>)</span> &#123;</span><br><span class="line">    <span class="comment">// 寻找当前节点的父节点是否为自己，不是的话表示还没找到</span></span><br><span class="line">    <span class="comment">// 开始进行路径压缩优化</span></span><br><span class="line">    <span class="comment">// 假设当前节点父节点为 A</span></span><br><span class="line">    <span class="comment">// 将当前节点挂载到 A 节点的父节点上，达到压缩深度的目的</span></span><br><span class="line">    <span class="keyword">while</span> (p != <span class="built_in">this</span>.parent[p]) &#123;</span><br><span class="line">      <span class="built_in">this</span>.parent[p] = <span class="built_in">this</span>.parent[<span class="built_in">this</span>.parent[p]]</span><br><span class="line">      p = <span class="built_in">this</span>.parent[p]</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> p</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">isConnected</span>(<span class="params">p, q</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.find(p) === <span class="built_in">this</span>.find(q)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="comment">// 合并</span></span><br><span class="line">  <span class="function"><span class="title">union</span>(<span class="params">p, q</span>)</span> &#123;</span><br><span class="line">    <span class="comment">// 找到两个数字的父节点</span></span><br><span class="line">    <span class="keyword">let</span> i = <span class="built_in">this</span>.find(p)</span><br><span class="line">    <span class="keyword">let</span> j = <span class="built_in">this</span>.find(q)</span><br><span class="line">    <span class="keyword">if</span> (i === j) <span class="keyword">return</span></span><br><span class="line">    <span class="comment">// 判断两棵树的深度，深度小的加到深度大的树下面</span></span><br><span class="line">    <span class="comment">// 如果两棵树深度相等，那就无所谓怎么加</span></span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">this</span>.rank[i] &lt; <span class="built_in">this</span>.rank[j]) &#123;</span><br><span class="line">      <span class="built_in">this</span>.parent[i] = j</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (<span class="built_in">this</span>.rank[i] &gt; <span class="built_in">this</span>.rank[j]) &#123;</span><br><span class="line">      <span class="built_in">this</span>.parent[j] = i</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      <span class="built_in">this</span>.parent[i] = j</span><br><span class="line">      <span class="built_in">this</span>.rank[j] += <span class="number">1</span></span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="堆"><a href="#堆" class="headerlink" title="堆"></a>堆</h2><h3 id="概念-6"><a href="#概念-6" class="headerlink" title="概念"></a>概念</h3><p>堆通常是一个可以被看做一棵树的数组对象。</p>
<p>堆的实现通过构造<strong>二叉堆</strong>，实为二叉树的一种。这种数据结构具有以下性质。</p>
<ul>
<li>任意节点小于（或大于）它的所有子节点</li>
<li>堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层从左到右填入。</li>
</ul>
<p>将根节点最大的堆叫做<strong>最大堆</strong>或<strong>大根堆</strong>，根节点最小的堆叫做<strong>最小堆</strong>或<strong>小根堆</strong>。</p>
<p>优先队列也完全可以用堆来实现，操作是一模一样的。</p>
<h3 id="实现大根堆"><a href="#实现大根堆" class="headerlink" title="实现大根堆"></a>实现大根堆</h3><p>堆的每个节点的左边子节点索引是 <code>i * 2 + 1</code>，右边是 <code>i * 2 + 2</code>，父节点是 <code>(i - 1) /2</code>。</p>
<p>堆有两个核心的操作，分别是 <code>shiftUp</code> 和 <code>shiftDown</code> 。前者用于添加元素，后者用于删除根节点。</p>
<p><code>shiftUp</code> 的核心思路是一路将节点与父节点对比大小，如果比父节点大，就和父节点交换位置。</p>
<p><code>shiftDown</code> 的核心思路是先将根节点和末尾交换位置，然后移除末尾元素。接下来循环判断父节点和两个子节点的大小，如果子节点大，就把最大的子节点和父节点交换。</p>
<p><img src="https://user-gold-cdn.xitu.io/2018/6/15/164009e58a5a21f8?w=537&h=394&f=png&s=77222"></p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MaxHeap</span> </span>&#123;</span><br><span class="line">  <span class="function"><span class="title">constructor</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.heap = []</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">size</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.heap.length</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">empty</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.size() == <span class="number">0</span></span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">add</span>(<span class="params">item</span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>.heap.push(item)</span><br><span class="line">    <span class="built_in">this</span>._shiftUp(<span class="built_in">this</span>.size() - <span class="number">1</span>)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">removeMax</span>(<span class="params"></span>)</span> &#123;</span><br><span class="line">    <span class="built_in">this</span>._shiftDown(<span class="number">0</span>)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">getParentIndex</span>(<span class="params">k</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">parseInt</span>((k - <span class="number">1</span>) / <span class="number">2</span>)</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">getLeftIndex</span>(<span class="params">k</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> k * <span class="number">2</span> + <span class="number">1</span></span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">_shiftUp</span>(<span class="params">k</span>)</span> &#123;</span><br><span class="line">    <span class="comment">// 如果当前节点比父节点大，就交换</span></span><br><span class="line">    <span class="keyword">while</span> (<span class="built_in">this</span>.heap[k] &gt; <span class="built_in">this</span>.heap[<span class="built_in">this</span>.getParentIndex(k)]) &#123;</span><br><span class="line">      <span class="built_in">this</span>._swap(k, <span class="built_in">this</span>.getParentIndex(k))</span><br><span class="line">      <span class="comment">// 将索引变成父节点</span></span><br><span class="line">      k = <span class="built_in">this</span>.getParentIndex(k)</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">_shiftDown</span>(<span class="params">k</span>)</span> &#123;</span><br><span class="line">    <span class="comment">// 交换首位并删除末尾</span></span><br><span class="line">    <span class="built_in">this</span>._swap(k, <span class="built_in">this</span>.size() - <span class="number">1</span>)</span><br><span class="line">    <span class="built_in">this</span>.heap.splice(<span class="built_in">this</span>.size() - <span class="number">1</span>, <span class="number">1</span>)</span><br><span class="line">    <span class="comment">// 判断节点是否有左孩子，因为二叉堆的特性，有右必有左</span></span><br><span class="line">    <span class="keyword">while</span> (<span class="built_in">this</span>.getLeftIndex(k) &lt; <span class="built_in">this</span>.size()) &#123;</span><br><span class="line">      <span class="keyword">let</span> j = <span class="built_in">this</span>.getLeftIndex(k)</span><br><span class="line">      <span class="comment">// 判断是否有右孩子，并且右孩子是否大于左孩子</span></span><br><span class="line">      <span class="keyword">if</span> (j + <span class="number">1</span> &lt; <span class="built_in">this</span>.size() &amp;&amp; <span class="built_in">this</span>.heap[j + <span class="number">1</span>] &gt; <span class="built_in">this</span>.heap[j]) j++</span><br><span class="line">      <span class="comment">// 判断父节点是否已经比子节点都大</span></span><br><span class="line">      <span class="keyword">if</span> (<span class="built_in">this</span>.heap[k] &gt;= <span class="built_in">this</span>.heap[j]) <span class="keyword">break</span></span><br><span class="line">      <span class="built_in">this</span>._swap(k, j)</span><br><span class="line">      k = j</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="function"><span class="title">_swap</span>(<span class="params">left, right</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">let</span> rightValue = <span class="built_in">this</span>.heap[right]</span><br><span class="line">    <span class="built_in">this</span>.heap[right] = <span class="built_in">this</span>.heap[left]</span><br><span class="line">    <span class="built_in">this</span>.heap[left] = rightValue</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="尾调用"><a href="#尾调用" class="headerlink" title="尾调用"></a>尾调用</h2><p><a target="_blank" rel="noopener" href="https://es6.ruanyifeng.com/#docs/function#%E5%B0%BE%E8%B0%83%E7%94%A8%E4%BC%98%E5%8C%96">尾调用</a><br>尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用记录，取代外层函数的调用记录就可以了。对于尾递归来说，由于只存在一个调用记录，所以永远不会发生”栈溢出”错误。</p>
<blockquote class="pullquote mindmap mindmap-lg"><ul>
<li>数据结构<ul>
<li>树与二叉树<ul>
<li>二叉树<ul>
<li>完全二叉树</li>
<li>满二叉树</li>
<li>二叉搜索树</li>
<li>平衡二叉搜索树<ul>
<li>红黑树</li>
</ul>
</li>
<li>特点<ul>
<li>遍历方式<ul>
<li>广度优先</li>
<li>深度优先<ul>
<li>前序遍历</li>
<li>中序遍历</li>
<li>后序遍历</li>
</ul>
</li>
</ul>
</li>
<li>顺序和链式</li>
</ul>
</li>
</ul>
</li>
<li>哈夫曼叔</li>
<li>字典树</li>
</ul>
</li>
<li>排序<ul>
<li>O(n^2)<ul>
<li>冒泡</li>
<li>插入</li>
<li>选择</li>
</ul>
</li>
<li>O(nlog(n))<ul>
<li>快速排序</li>
<li>归并排序</li>
</ul>
</li>
<li>O(n)<ul>
<li>桶排序</li>
<li>基数排序</li>
<li>计数排序</li>
</ul>
</li>
</ul>
</li>
<li>受限线性表<ul>
<li>栈<ul>
<li>顺序和链式都可以实现 先进后出</li>
<li>实际应用<ul>
<li>浏览器的前进和后退</li>
<li>括号匹配</li>
<li>表达式计算</li>
</ul>
</li>
</ul>
</li>
<li>堆<ul>
<li>大顶堆</li>
<li>小顶堆</li>
</ul>
</li>
<li>队列<ul>
<li>普通队列 顺序和链式都可以实现 先进后出</li>
<li>双边队列 入口和出口都可以进队和出队</li>
<li>优先级队列 根据优先级来出队</li>
<li>实际应用 LRU cache</li>
</ul>
</li>
</ul>
</li>
<li>非受限线性表<ul>
<li>顺序结构<ul>
<li>数组<ul>
<li>支持 O(1) 的随机访问</li>
<li>平均为 O(n) 的插入和删除</li>
<li>警惕越界错误，导致 Stack Over Flow</li>
</ul>
</li>
</ul>
</li>
<li>链式结构<ul>
<li>单链表<ul>
<li>不支持随机访问，需要遍历去访问结点</li>
<li>插入和删除只需要移动指针，时间复杂度</li>
<li>每个结点需要额外的空间存储指针，需要的内存比数组大 为 O(1)</li>
</ul>
</li>
<li>双链表<ul>
<li>在单链表的基础上，除头结点外，每个结点多了一个存放前驱结点内存地址的指针</li>
</ul>
</li>
<li>循环链表<ul>
<li>尾节点指针指向头结点</li>
</ul>
</li>
<li>静态链表<ul>
<li>借助数组，伴随指向后继结点的指针</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</blockquote>
<script type="text/javascript" src="https://cdn.jsdelivr.net/npm/kity@2.0.4/dist/kity.min.js"></script><script type="text/javascript" src="https://cdn.jsdelivr.net/npm/kityminder-core@1.4.50/dist/kityminder.core.min.js"></script><script defer="true" type="text/javascript" src="https://cdn.jsdelivr.net/npm/hexo-simple-mindmap@0.2.0/dist/mindmap.min.js"></script><link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/npm/hexo-simple-mindmap@0.2.0/dist/mindmap.min.css">
    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/%E7%AE%97%E6%B3%95%E6%80%9D%E6%83%B3/" rel="tag"># 算法思想</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2022/07/10/%E4%BB%A3%E7%A0%81%E4%B8%AD%E6%B3%A8%E6%84%8F%E9%97%AE%E9%A2%98/" rel="prev" title="代码中注意问题">
                  <i class="fa fa-chevron-left"></i> 代码中注意问题
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/2022/07/27/vscode%E5%BF%AB%E6%8D%B7%E9%94%AE/" rel="next" title="vscode快捷键">
                  vscode快捷键 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 
  <span itemprop="copyrightYear">2023</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">郭泽</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.6.0/jquery.min.js" integrity="sha256-/xUj+3OJU5yExlq6GSYGSHk7tPXikynS7ogEvDej/m4=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.5.7/jquery.fancybox.min.js" integrity="sha256-yt2kYMy0w8AbtF89WXb2P1rfjcP/HTHLT7097U8Y5b8=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/next-boot.js"></script><script src="/js/bookmark.js"></script>

  
<script src="https://cdnjs.cloudflare.com/ajax/libs/hexo-generator-searchdb/1.4.0/search.js" integrity="sha256-vXZMYLEqsROAXkEw93GGIvaB2ab+QW6w3+1ahD9nXXA=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>

  <script class="next-config" data-name="pdf" type="application/json">{"object_url":{"url":"https://cdnjs.cloudflare.com/ajax/libs/pdfobject/2.2.8/pdfobject.min.js","integrity":"sha256-tu9j5pBilBQrWSDePOOajCUdz6hWsid/lBNzK4KgEPM="},"url":"/lib/pdf/web/viewer.html"}</script>
  <script src="/js/third-party/tags/pdf.js"></script>

  <script class="next-config" data-name="mermaid" type="application/json">{"enable":true,"theme":{"light":"default","dark":"dark"},"js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mermaid/9.1.3/mermaid.min.js","integrity":"sha256-TIYL00Rhw/8WaoUhYTLX9SKIEFdXxg+yMWSLVUbhiLg="}}</script>
  <script src="/js/third-party/tags/mermaid.js"></script>

  <script src="/js/third-party/fancybox.js"></script>


  





</body>
</html>
